/**
 * Description:
 * Date: 2025-10-27
 * Time: 21:20
 */
public class Test {
    public static void main1(String[] args) {
        //算法效率分 时间效率 和 空间效率
        //时间效率：时间复杂度，衡量一个算法的运行速度
        //空间效率：空间复杂度，衡量一个算法在运行过程中所需的额外空间内存
    }

    public static void main2(String[] args) {
        //时间复杂度的计算公式：大O的渐进表示法
        // 结果是一个估值，不能精确表示

        //推导大O阶方法
        // 1.用常数1代替式子中的所有加法常数
        // 2.修改后的表达函数中，只保留最高此项
        // 3.若最高次项存在且常数因子不为1，则去掉常数因子
    }

    void func1(int N){
     int count = 0;

     //执行N^2次
     for (int i = 0; i < N ; i++) {
            for (int j = 0; j < N ; j++) {
                count++;
            }
        }
     //执行2*N次
     for (int k = 0; k < 2 * N ; k++) {
            count++;
        }
     int M = 10;
     //执行10次
     while ((M--) > 0) {
            count++;
        }
        System.out.println(count);

        //则执行次数的函数表达式为：F(N) = N^2+2*N+10
        //用大O阶表达式为： 去掉了一些对结果影响不大的项，得到了一个近似值
        //1.F(N) = N^2+2*N+1
        //2.F(N) = N^2
        //3.F(N) = N^2
        //所以最终的时间复杂度为O(N^2)
        //平时所计算的时间复杂度一般都是计算最坏的情况下，程序执行的次数
     }


    void func2(int N) {
        int count = 0;
        //执行2*N次
        for (int k = 0; k < 2 * N ; k++) {
        count++;
        }
        //执行10次
        int M = 10;
        while ((M--) > 0) {
        count++;
        }
        System.out.println(count);

        //F(N) = 2*N+10;
        //大O阶表达式:F(N) = N
        //时间复杂度为:O(N)

    }

    void func3(int N, int M) {
        int count = 0;
        //执行M次
        for (int k = 0; k < M; k++) {
        count++;
        }
        //执行N次
        for (int k = 0; k < N ; k++) {
        count++;
        }
        System.out.println(count);

        //F(N) = M + N
        //时间复杂度：O(M+N)
    }

    void func4(int N) {
        int count = 0;
        //执行100次
        for (int k = 0; k < 100; k++) {
        count++;
        }
        System.out.println(count);

        //F(N) = 100
        //时间复杂度：O(1)
    }

    void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--) {
        boolean sorted = true;
        for (int i = 1; i < end; i++) {
            if (array[i - 1] > array[i]) {
                int tmp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = tmp;
                sorted = false;
            }
        }
        if (sorted == true) {
            break; }
        }
        //F(N) = 1 + 2 + ... + N-1 = (N^2-N)/2 = N^2
        //时间复杂度：O(N^2)

        //空间复杂度：O(1)  除了参数的数组固定给的空间外，都是常数个的内存空间创建。空间复杂度的计算遵循大O阶表达式
    }

    int binarySearch(int[] array, int value) {
        //分析算法过程来计算执行次数
        int begin = 0;
        int end = array.length - 1;
        while (begin <= end) {
            int mid = begin + ((end - begin) / 2);
            if (array[mid] < value)
                begin = mid + 1;
            else if (array[mid] > value)
                end = mid - 1;
            else
                return mid;
        }
        return -1;

        //每次执行都会少一半范围，当范围为1时找到
        //N/2^x = 1 --> x = logN
        //时间复杂度：O(LogN)
    }


    //递归的时间复杂度计算公式：N = 递归的次数 * 每次递归执行的次数
    long factorial(int N) {
        return N < 2 ? N : factorial(N-1) * N;

        //递归了N次，每次递归的次数为1
        //F(N) = 1*N
        //时间复杂度：O(N)

        //空间复杂度：递归了N次，开辟了N个内存空间，每个内存空间使用了常数个空间
        //O(N)
    }


}


